package DP;

/**
 * 完全背包问题
 * 题目描述
 * 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
 * 小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。
 * 输入描述
 * 第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间
 * 接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
 * 输出描述
 * 输出一个整数，表示最大价值。
 */

import java.util.Scanner;

/**
 * 一刷
 */
public class CompletePack {
    private static void testCompletePack() {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) { // 遍历物品
            for (int j = weight[i]; j <= bagWeight; j++) { // 顺序遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        for (int maxValue : dp) {
            System.out.println(maxValue + "   ");
        }
    }
}

/**
 * 二刷
 */
//二维
class bag {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();//重量
        int[] weight = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int[][] dp = new int[n][v + 1];
        for (int j = 0; j <= v; j++) {
            dp[0][j] = (j / weight[0]) * value[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= v; j++) {
                if (j >= weight[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[n - 1][v]);
    }
}
//一维
class completebag {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int v = sc.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        for (int i = 0; i < n; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int[] dp = new int[v + 1];
        for (int j = 0; j <= v; j++) {
            dp[j] = (j / weight[0]) * value[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= v; j++) {
                if (j >= weight[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
        System.out.println(dp[v]);
    }
}
